#include <stdio.h>
#include <math.h>
#include <stdlib.h>

//https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

typedef struct ListNode {
    int val;
    struct ListNode *next;
}ListNode;

ListNode* partition(ListNode* pHead, int x) {
    ListNode *preHeadSmall = (ListNode *) malloc(sizeof(ListNode));
    ListNode *preHeadBig = (ListNode *) malloc(sizeof(ListNode));
    ListNode *curSmall = preHeadSmall;
    ListNode *curBig = preHeadBig;
    ListNode *cur = pHead;
    while (cur) {
        if (cur->val < x) {
            curSmall->next = cur;
            curSmall = curSmall->next;
        } else {
            curBig->next = cur;
            curBig = curBig->next;
        }
        cur = cur->next;
    }
    curSmall->next = NULL;
    curBig->next = NULL;
    curSmall->next = preHeadBig->next;
    return preHeadSmall->next;
}

int main() {

    return 0;
}